struct Node
{
    int val;
    int weight;
} Node;

int computeWeight(int val)
{
    int weight = 0;
    while (val > 1)
    {
        if (val % 2 == 0)
        {
            val /= 2;
        }
        else
        {
            val = val * 3 + 1;
        }
        weight++;
    }
    return weight;
}

int compare(const void *a, const void *b)
{
    struct Node *p = (struct Node *)a;
    struct Node *q = (struct Node *)b;

    // 优先按照权重升序排序
    if (p->weight < q->weight)
    {
        // 前面小的就不交换(-1)！！！
        return -1;
    }

    if (p->weight > q->weight)
    {
        return 1;
    }

    // 权重相等比较值本身
    return (p->val - q->val);
}

int getKth(int lo, int hi, int k)
{
    int len = hi - lo + 1;
    int i;
    int res;
    struct Node *nums = (int *)malloc(sizeof(struct Node) * len);
    // printf("hi:%d lo:%d len:%d\n",hi,lo,len);
    for (i = lo; i <= hi; i++)
    {
        nums[i - lo].val = i;
        nums[i - lo].weight = computeWeight(i);
        // printf("val: %d weight %d ", i, computeWeight(i));
    }
    // printf("\n");
    qsort(nums, len, sizeof(struct Node), compare);

    // for(i = 0; i < len; i++) {
    //     printf("nums[%d].val %d weight %d\n", i, nums[i].val, nums[i].weight);
    // }
    // printf("\n");

    res = nums[k - 1].val;
    free(nums);
    return res;
}